暗号化事始め

　今回は暗号化についてです。小難しい理論なんかの解説は他のサイトに譲るとして、ここでは実際にどのようにコーディングするかを紹介していきます。

Introduction
共通鍵暗号

簡単な共通鍵暗号
暗号化の強い味方、xor
ちょっと手の込んだ共通鍵暗号

ハッシュ
ハッシュを使ってデータの信頼性をあげる
まとめ

Introduction

　最初に、なぜ暗号化なんてするのかを考えてみます。
　例えば、PC ゲームを作って配布するとします。ゲームなので、画像やら音楽やらのファイルが必要になるでしょう。そいつらも当然一緒に配布しますが、個別のファイルとして配布すると、ダウンロードしたユーザはそれらをのぞくことができます。特に、MIDI や BMP をそのまま入れておくと簡単にそのデータだけコピーできてしまいます。エロゲで、ゲームをプレイしなくてもエッチな CG がみられてしまうわけです。これではちょっとまずいですね。ではどうすればいいのでしょう。
　とりあえず、初心者をだますには拡張子を変えるのが効果的です。 .bmp を .aaa などに変えておけば、ダブルクリックで開く心配はなくなります。ですが、ちょっと PC をかじった程度の人ならば、バイナリエディタで中身をみて、ファイルの中身を判断できてしまいます。
　では、EXE の中にリソースとして詰め込むのはどうでしょう。確かにこれだとのぞかれにくくはなりますが、今度は開発の時点で問題が生じます。それは、データに変更があったとき、EXE を再度ビルドしなければならないという点です。これはさすがに面倒ですよね。
　そこで登場するのが、『データの暗号化』です。簡単な計算でもデータの隠蔽をはかることができ、ゲーム配布の際には大いに役立つでしょう。次の章からは具体的にその方法を追っていきます。

共通鍵暗号

　暗号方式には大きく分けて『共通鍵暗号』と『公開鍵暗号』があります。後者は理論が難しいので、今回は扱いません。そもそも鍵とはなんぞやというと、平文（暗号化前のデータを俗にこう呼ぶ）から暗号文を生成するための、任意のデータということになります。鍵のサイズは、0 でなければ平文より大きくても小さくてもかまいません。
　さて、ここからが共通鍵暗号の真意ですが、共通鍵暗号の場合は、暗号化するために使った鍵を使って、暗号文を平文に戻すことができます。具体的には、

E = P(K)

P = E(K)

　が成り立つということです。ここで、E は暗号文、P は平文、K は鍵です。暗号化するときと、暗号化されたデータを元に戻す（復号という。『化』はつけないのが正しい）に同じ鍵を用いる、というのが、共通鍵暗号の最大の特徴です。

簡単な共通鍵暗号

　ものは試しということで、簡単な暗号化関数を作ってみます。次がそのコードです。

void enc01(void *plain, unsigned len, const void *key, unsigned klen)
{
	unsigned i, j;

	for( i = 0; i < len; i++ ) {
		for( j = 0; j < klen; j++ ) {
			((char*) plain)[i] ^= ((char*) key)[j];
		}
	}
}

　引数は左から平文へのポインタ、平文の長さ、鍵へのポインタ、鍵の長さです。これらを指定してこの関数を呼び出せば、簡単な暗号を施してくれます。試しに、次のコードを実行させてみます。


void main()
{
	char plain[] = "Through the years and far away";
	const char key[] = "star";
	int n;

	n = strlen( plain );
	enc01(plain, n, key, strlen(key));
	fprintf(stdout, "%s\n", plain);
	enc01(plain, n, key, strlen(key));
	fprintf(stdout, "%s\n", plain);
}

出力結果

@|f{as|4`|q4mqufg4uzp4ruf4ucum
Through the years and far away

　する必要もないかも知れませんが、コードの解説をします。まず、一回 enc01 を呼び出し、結果を出力しています。意味不明な文字列が出力されました。この関数は入力と出力を同じバッファにしますので、 plain の値が直接書き換えられます。そして、もう一度、同じ鍵を使って enc01 関数を呼び出します。その結果を出力すると、最初に用意した平文とぴたりと重なります。同じ鍵を使って 2 回暗号化することで、元に戻ることを確認できました。

暗号化の強い味方、xor

　解説に移る前に、一つ覚えて欲しい事柄があります。それは、xor の特性です。中～上級者向け講座なので xor の意味は説明はしませんが、これは他の論理演算と大きくことなる点があります。それは、同じ値で 2 回 xor をとると、もとの値に戻るという点です。 Windows の電卓を起動して、関数電卓モードにしてください。まず、65 を打ち、xor ボタンを押して 45 を打ち、結果を表示してみてください。108 になりましたね。そこで、もう一度 xor ボタンを押して 45 を打ち、計算してみてください。65 に戻ったでしょう。これが、同じ値で 2 回～の意味です。では、今度は 108 を打ち、xor を押して 65 を打ち、計算してみてください。答えは 45 になりましたね。この 3 つの数値には一連の関係があり、2 値が求まれば残り 1 値が求まることを意味します。これは、他の and などの論理演算にはない特性です。
　さて、今回はこの xor の特性をうまく使っています。2 回～のところです。暗号化部分では、1 バイトごとに鍵の各バイトとの xor をとっているだけです。これを数学的に見てみると、

E = P ^ K1 ^ K2 ^ ... ^ Kn

　ということになります。K1, K2, ... Kn は鍵のバイトです。さて、今度は復号をしてみます。上の結果の E に、同じ鍵で暗号化すると、次のようになります。

P = E ^ K1 ^ K2 ^ ... ^ Kn = P ^ K1 ^ K2 ^ ... Kn ^ K1 ^ K2 ^ ... ^ Kn

　太字の部分が結論です。つまり、同じ鍵で二回 xor をとっているので、結果的にもとに戻っているのです。どうでしょう、すっきりしたでしょう？

ちょっと手の込んだ共通鍵暗号

　上の例で完璧じゃねーか！　という人は、ちょっと待ってください。よく見ると、平文と暗号文との間にある関係が見えてきます。平文の半角スペースの位置を見てください。5 つありますね。そして、真上の暗号化した部分で、平文のスペースがあった位置を見てください。なんと、すべて 4 に置き換わっていますね。他の文字についても同じです。つまり、A を暗号化すると B になる、といったように、暗号結果が平文から完全に決まってしまっているのです。試しに、『aaaaaaaa』を暗号化してみてください。きっと、『uuuuuuuu』になるでしょう。これだと、暗号化の強度がなってないということになります。文章の場合は、文字の出現頻度から簡単に平文が割り出せてしまうそうです。今度はこの問題を回避する方法を模索してみましょう。
　なぜこのようなことになるかというと、同じに文字に対して同じ鍵で暗号化するからいけないのです。同じ文字を暗号化する際でも、使う鍵が違えば結果はことなります。ただし、渡す鍵は同じでなければなりません。さてどうしましょう。
　常套手段として、鍵に加えて、直前のデータの暗号化結果を暗号化に使うという方法があります。 CBC 暗号といいます。まずはコードを見てみましょう。

void enc02_e(void *p, unsigned len, const void *key, unsigned klen)
{
	unsigned i, j;
	char IV = 0x7a;

	for( i = 0; i < len; i++ ) {
		((char*) p)[i] ^= IV;
		for( j = 0; j < klen; j++ ) {
			((char*) p)[i] ^= ((char*) key)[j];
		}
		IV = ((char*) p)[i];
	}
}

　先ほどと違うのは、鍵と xor をとるだけでなく、暗号結果とも xor をとるところです。ただし、一番最初のバイトには暗号結果など存在しないので、特別に初期ベクトル（initial vector）IV を適当な数値で用意してやります。暗号結果は IV に代入し、次の暗号化セクションで使用しています。さて、これで暗号化するとどうなるでしょう。呼び出し方は先ほどと同じなので、ソースは割愛します。鍵は同じく『star』を使用します。

:F [:I5alX5D1W0q{O=H.oy

　上が結果です。さっきよりも意味不明な文字、というより文字でなくなっていますね。これならこのデータから平文を求めるのは、鍵なしでは困難といえるでしょう。
　さて、お次は復号です。先ほどの例では、暗号にも復号にも同じ関数を使っていました。これは、xor の特性をうまく利用したからでしたね。ですが、今回はそう簡単にはいきません。なぜなら、内部で少し変わった処理が入ってしまっているからです。よって、復号には復号専用の関数を作らなければなりません。ですが、今回も xor の特性を使っていることは変わらないので、うまく 2 回 xor をかけて、打ち消すようにコーディングします。

void enc02_d(void *p, unsigned len, const void *key, unsigned klen)
{
	unsigned i, j;
	char IV = 0x7a, t;

	for( i = 0; i < len; i++ ) {
		t = ((char*) p)[i];
		((char*) p)[i] ^= IV;
		for( j = 0; j < klen; j++ ) {
			((char*) p)[i] ^= ((char*) key)[j];
		}
		IV = t;
	}
}

　こんな感じです。暗号結果をどこで使うか、またその結果を次はどうするかをちょこっと考えれば作れる代物です。この関数に、先ほどの結果の入ったバッファと同じ鍵を指定して呼び出せば、平文がちゃんと復元できます。

ハッシュ

　暗号化ではありませんが、似たようなもので『ハッシュ』というものがあります。ハッシュのもともとの意味は『細かく切り刻む』だそうです。ハッシュの特性として、次のようなものがあります。

任意長のデータ P から固定長のデータ H を導く
P から H は簡単に求まるが、H から P を求めるのは困難（一方向性）。

　ハッシュというのは、普通固定長です。128 ビットとか 320 ビットとかそんな感じです。もとのデータはいくらでもかまいません。1 バイトだろうと 10GB だろうと、ハッシュ関数にかければ結果は固定長になります。
　もう一つの特性として、ハッシュ値から元データを算出することが困難となります。これは普通に考えれば解りますよね。例えば、10GB のデータを 8 バイトのハッシュ値にしたとします。つまり、10G - 8 バイトのデータは失われたこととなります。その失われた 10G - 8 バイトを求める方法などありません。逆に、2 バイトのデータから 8 バイトのハッシュ値を求めたとします。すると、どこからともなく 6 バイト分のデータが現れて、ハッシュ値にくっついた感じになります。その冗長な 6 バイトを正しく取り除くのは困難、というわけです。
　ところで、こんなものを何に使うのかというのを説明しておきます。私が考えるところ、例えばファイルの比較なんかに使えるんじゃないかと思います。ここに 10GB のファイルがあるとします。そして、次から次へと 10GB のファイルが流れてくるとします。今、もとあるファイルと同じファイルが来た場合は破棄し、違うものであれば保存したいとします。単純に考えると、10GB の中身を比較して、中身が同じかどうか調べる必要があります。ですが、10GB もあると、さすがに比較に時間がかかります。そこで、まず最初のファイルから 8 バイトのハッシュ値を求めます。次に、流れてきたファイルのハッシュ値を求めます。中身が同じファイルなら、ハッシュ値は必ず等しくなります。ここで、流れてきたファイルのハッシュ値ともとのファイルのハッシュ値が同じなら、中身は同じと判断できます。次に流れてきたファイルも同様にハッシュ値を計算し、もとのハッシュ値と比較します。これなら、比較は 8 バイト分だけなので、非常に高速に比較できます。
　ところで、ハッシュにも問題があります。任意長のデータを固定長のデータに凝縮するので、どうしてもコリジョン、つまり値が衝突することがあります。 128 ビットくらいのハッシュ値なら衝突する危険性は減るとはいえ、絶対になくなるわけではありません。これはハッシュの宿命です。どうしてもコリジョンが起きてはまずいときには、まずハッシュ値でデータを検査し、それをパスしたデータのみ、ハッシュ値を使わないでデータを検査するようにすれば大丈夫です。ハッシュ値のみのときより若干時間はかかりますが、元データだけで検査するよりかはずっと速いと思います。

ハッシュを使ってデータの信頼性をあげる

　最後に、ハッシュを使ってデータの信頼性をあげる方法を示しておきます。
　とあるプログラムは、外部ファイルにおいてある独自フォーマットのファイルを必要とします。ただし、中身が壊れている、あるいは人為的に書き換えられているかも知れません。ですが、バイナリファイルなので、正しいデータなのか本当に壊れているのか判断できません。さて、こういうときに威力を発揮するのがハッシュです。
　まず、書き出したファイルのハッシュ値を計算します。ここでは同じように 8 バイトとします。その計算結果を、ファイルのじゃまにならないところ、さしずめ先頭か末尾に書き込んでおきます。そして、次回そのファイルを読み込むとき、実際あったデータとあとから追加したハッシュ値を分けて読み込みます。その読み込んだデータのハッシュ値を計算し、別に読み込んだハッシュ値と比較して、一致すれば前回書き込んだときと同じ内容であると判断できます。人為的に壊されては困るファイルには、ハッシュ値をくっつけておくといいでしょう。

まとめ

共通鍵暗号は、暗号化と復号に同じ鍵を用いる暗号化方式である
xor は暗号の友
ハッシュ値はデータの信頼性を高めてくれる強い味方

　ちなみに、最後の方で紹介したデータの整合性チェックには、普通は CRC（Cyclic Redundancy Check）と呼ばれる、似たような方法もあります。一般に、CRC のほうが検査サイズが小さいようです。

2008/06/05
ソースが一部間違っているとのご指摘を受け、修正しました。

[戻る]

[トップへ戻る]